package m202403.d13;

import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/3/13 15:57
 */
//120. 三角形最小路径和
public class Q120 {
    public static void main(String[] args) {
        List<List<Integer>> lists = List.of(
                List.of(2),
                List.of(3, 4),
                List.of(6, 5, 7),
                List.of(4, 1, 8, 3)
        );
        int i = new Q120().minimumTotal(lists);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int[][] dp = new int[m][m];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < i + 1; j++) {
                Integer temp = triangle.get(i).get(j);
                if (j == i ) {
                    dp[i][j] = dp[i - 1][j - 1] + temp;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1] + temp, dp[i - 1][j] + temp);
                }

            }
        }
        int r = dp[m - 1][0];
        for (int i = 0; i < dp[m - 1].length; i++) {
            r = Math.min(dp[m - 1][i], r);
        }
        return r;
    }
}
